package LCR;

public class validPalindrome {
    public static void main(String[] args) {
        System.out.println(validPalindrome("cupuufxoohdfpgj" +
                "dmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupucu"));
    }
    public static boolean validPalindrome(String s) {
        for(int left = 0, right = s.length() - 1; left < right; left++, right--){
            // 如果不相等，则分两种情况：删除左边的元素，或者右边的元素，再判断各自是否回文，满足一种即可。
            if(s.charAt(left) != s.charAt(right))
                return isPalindrome(s, left+1, right) || isPalindrome(s, left, right - 1);
        }
        return true;
    }

    // 判断字符串 s 的 [left, right] 是否回文
    private static boolean isPalindrome(String s, int left, int right){
        while (left < right){
            if (s.charAt(left++) != s.charAt(right--))
                return false;
        }
        return true;
    }
}
